package org.nowcoder.leetcode.linkedList;

import java.util.ArrayDeque;

/**
 * Title  : 25. Reverse Nodes in k-Group
 * Source : https://leetcode.cn/problems/reverse-nodes-in-k-group/?envType=study-plan-v2&envId=top-interview-150
 * Author : XrazYang
 * Date   : 2023-08-01
 */
public class LeetCode_25 {
    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        //边界条件
        if (head.next == null) {
            return head;
        }

        //借助数据结构栈，翻转
        ArrayDeque<ListNode> sta = new ArrayDeque<>();
        int count = 0;
        ListNode p = head, q = null; //q表示该分组的上一个结点
        while (p != null) {
            if (count < k) { //k个结点一组
                sta.push(p);
                count++;
                p = p.next;
            }
            if (count == k) { //链表拼接
                while (!sta.isEmpty()) {
                    ListNode temp = sta.pop();
                    if (q == null) { //处理头结点
                        head = temp;
                    } else {
                        q.next = temp;
                    }
                    q = temp;
                }
                q.next = p;
                count = 0;
            }
        }
        return head;
    }
}
